package sort;


import java.util.Comparator;
import java.util.PriorityQueue;

public class AllSortHere {
    public static void main(String[] args) {
        PriorityQueue<Integer> p = new PriorityQueue<>(3,new MyCom());
        //默认小根堆  改为大根堆需要自定义比较器并且指定优先队列的大小
        p.add(1);
        p.add(2);
        p.add(3);
        p.add(4);
        p.add(5);
        System.out.println(p.peek());
    }

    static class MyCom implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }


    /*
    *冒泡排序
    * */
    public static void MPSort(int[] nums){
        if (nums.length<2){
            return;
        }
        for (int i=0;i<nums.length;i++){
            for (int j=0;j<nums.length-i-1;j++){
                if (nums[j] > nums[j+1]){
                    int temp=nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }

    /*
    * 选择排序:每次找出最大/最小的数，然后将其放在未排序区最左/最右
    * */
    public static void choseSort(int[] nums){
        if (nums.length<2){
            return;
        }
        for (int a = 0;a<nums.length-1;a++){
            int minIndex = a;
            for (int b = a+1;b<nums.length;b++){
                minIndex = nums[b]<nums[minIndex] ? b:minIndex;
            }
            if (minIndex!=a){
                int temp = nums[a];
                nums[a] = nums[minIndex];
                nums[minIndex] = temp;
            }
        }
    }
    /*
    * 46 30 82 90 56 17 95 15
    * 46 30 82 90 56 17 95 15
    * 46 30 17 90 56 82 95 15
    * 46 30 17 15 56 82 95 90
    * */

    /*
    * 直接插入排序：将数组最右或者最左的数一个数看做有序区，然后依次向有序区插入一个数字
    * 内部调节使整个有序区继续保持有序，直到插入所有数字
    * */
    public static void insertSort(int[] nums){
        for (int a=1;a<nums.length;a++){
            for (int b= a;b>0;b--){
                if (nums[b] < nums[b-1]){
                    swap(nums,b,b-1);
                }


            }
        }
    }

    /*
    * 快速排序
    * */
    public static int[] quickSort(int[] a,int first,int last){
        if(first<last){                //至少两个位置
            //定义pivotIndex中间位置。partition是检索这个方法
            int pivotIndex=partition(a,first,last);
            quickSort(a,first,pivotIndex-1);              //排序左半边
            quickSort(a,pivotIndex+1,last);               //排序右半边
        }
        return a;
    }
    public static  int partition(int[] a,int left,int right){
        //对数组A下标从first到last中选一个主元，确定其位置，左边小于，右边大于。

        int pivot=a[left];//先定义区间数组第一个元素为主元
        int i=left;   //定义最低的索引low是first+1。比主元大一位
        int j=right;     //定义最高的索引high是last
        while(i!=j){   //当low小于high的位置时，执行以下循环
            while(a[j]>pivot&&i<j){//当high的索引上的值比主元大时，且索引大于low时
                j--;                      //寻找比主元小的值的位置索引
            }
            while(a[i]<=pivot&&i<j){//当low的索引上的值比主元小时，索引小于high时
                i++;                       //寻找比主元大的值的位置索引。
            }

            if(i<j){   //交换low和high的值
                int t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }

        a[left]=a[j];
        a[j]=pivot;
        return j;
    }


    public static int[] mergerTwoArr(int[] left,int[] right){
        int a=0,b=0;
        int[] res = new int[left.length+right.length];
        for (int x=0;x<res.length;x++){
            int ta = a>=left.length?Integer.MAX_VALUE:left[a];
            int tb = b>=right.length?Integer.MAX_VALUE:right[b];
            if (ta<tb){
                res[x] = ta;
                a++;
            }else {
                res[x] = tb;
                b++;
            }
        }
        return res;
    }


    /*
    * 归并排序
    * */
    public static void GBSort(int[] nums){

    }

    public static void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
